#include "MLClustering_BIRCH.h"
#include "MLClustering_KMeans.h"
_MYLABLIB_BEGIN


///////////////////////////////////////////////////////////////////////////
// CMLClustering_BIRCHMicroCluster
CMLClustering_BIRCHMicroCluster::CMLClustering_BIRCHMicroCluster()
{
	m_pDistFunc = NULL;
}

CMLClustering_BIRCHMicroCluster::~CMLClustering_BIRCHMicroCluster()
{
}

int CMLClustering_BIRCHMicroCluster::Create(const CMLDataSet& dataSet)
{
	int i;
	m_vLS.zero();
	m_vSS.zero();
	m_DataSet.Clear();
	if (dataSet.IsEmpty())
		return 0;

	// Insert all the data points
	for (i=0; i<dataSet.Count(); i++)
		Insert(dataSet.Get(i));

	return 0;
}

int CMLClustering_BIRCHMicroCluster::Insert(const CMLDataPoint& p)
{
	m_DataSet.Insert(p);
	m_vLS.add(p);
	m_vSS.add(p^2);
	return 0;
}


///////////////////////////////////////////////////////////////////////////
// CMLClustering_BIRCHCFTreeNode
CMLClustering_BIRCHCFTreeNode::CMLClustering_BIRCHCFTreeNode(void)
{
	m_pParentNode = NULL;
	m_pDistFunc = NULL;
}

CMLClustering_BIRCHCFTreeNode::~CMLClustering_BIRCHCFTreeNode(void)
{
}

int CMLClustering_BIRCHCFTreeNode::CreateFromMicroClusters(const CMLClustering_BIRCHMicroCluster* pMicroCluster, int nMicroIndex)
{
	CMLDataPoint p;
	m_nMicroClusterIndex = nMicroIndex;

	// Get the data point count
	m_nDatapointCount = pMicroCluster->GetDataPointCount();
	// Calculate the LS and SS
	m_vLS = pMicroCluster->GetLS();
	m_vSS = pMicroCluster->GetSS();
	return 0;
}

int CMLClustering_BIRCHCFTreeNode::CreateFromChildNodes(std::vector<CMLClustering_BIRCHCFTreeNode*>& vpChildNodes)
{
	int i;
	m_nMicroClusterIndex = -1;
	m_vLS.zero();
	m_vSS.zero();
	m_nDatapointCount = 0;
	
	for (i=0; i<(int)vpChildNodes.size(); i++)
	{
		// Merge the information of the child nodes
		m_vLS.add(vpChildNodes[i]->GetLS());
		m_vSS.add(vpChildNodes[i]->GetSS());
		m_nDatapointCount += vpChildNodes[i]->GetDatapointCount();
	}

	for (i=0; i<(int)vpChildNodes.size(); i++) 
	{
		// Set the parent node pointer
		vpChildNodes[i]->SetParentNode(this);
		m_vpChildNodes.push_back(vpChildNodes[i]);
	}
	return 0;
}

///////////////////////////////////////////////////////////////////////////
// CMLClustering_BIRCHCFTree
CMLClustering_BIRCHCFTree::CMLClustering_BIRCHCFTree(void)
{
	m_pRootNode = NULL;
	m_pDistFunc = NULL;
}

CMLClustering_BIRCHCFTree::~CMLClustering_BIRCHCFTree(void)
{
	Release();
}

int CMLClustering_BIRCHCFTree::Create(std::vector<CMLClustering_BIRCHMicroCluster*>& vpMicroClusters, int nLevelFactor)
{
	int i;
	m_nLevelFactor = nLevelFactor;

	// Create the leaf nodes by micro-clusters
	std::vector<CMLClustering_BIRCHCFTreeNode*> vpLeafNodes;
	vpLeafNodes.resize(vpMicroClusters.size());
	for (i=0; i<(int)vpMicroClusters.size(); i++)
	{
		const CMLClustering_BIRCHMicroCluster* pMicroCluster = vpMicroClusters[i];
		vpLeafNodes[i] = new CMLClustering_BIRCHCFTreeNode();
		vpLeafNodes[i]->SetDistFunc(GetDistFunc());
		vpLeafNodes[i]->CreateFromMicroClusters(pMicroCluster, i);
	}

	// Create high level nodes
	return ClusterParentNodes(vpLeafNodes);
}

int CMLClustering_BIRCHCFTree::ClusterParentNodes(std::vector<CMLClustering_BIRCHCFTreeNode*>& vChildNodes)
{
	int nRet;
	int i;
	int nK = (int)vChildNodes.size() / m_nLevelFactor;
	if (nK <= 1)
	{
		m_pRootNode = new CMLClustering_BIRCHCFTreeNode();
		m_pRootNode->SetDistFunc(GetDistFunc());
		m_pRootNode->CreateFromChildNodes(vChildNodes);
	}
	else
	{
		// Create the parent nodes
		std::vector<CMLClustering_BIRCHCFTreeNode*> vpParentNodes;
		vpParentNodes.resize((size_t)nK);
		for (i=0; i<nK; i++)
		{
			vpParentNodes[i] = new CMLClustering_BIRCHCFTreeNode();
			vpParentNodes[i]->SetDistFunc(GetDistFunc());
		}
		
		// Create the dataset to prepare the clustering
		std::map<CMLDataPoint, CMLClustering_BIRCHCFTreeNode*> mapNodeCenters;
		CMLDataSet centerDataSet;
		std::vector<double> centerWeights;
		int nTotalChildrenDataPoints = 0;

		centerDataSet.Resize((int)vChildNodes.size());
		for (i=0; i<(int)vChildNodes.size(); i++)
		{
			const CMLDataPoint& center = vChildNodes[i]->GetCenter();
			centerDataSet.Set(i, center);
			mapNodeCenters[center] = vChildNodes[i];
			nTotalChildrenDataPoints += vChildNodes[i]->GetDatapointCount();
		}

		// Calculate the weights for the centers
		centerWeights.resize(vChildNodes.size());
		for (i=0; i<(int)vChildNodes.size(); i++)
			centerWeights[i] = ((double)(vChildNodes[i]->GetDatapointCount())) / ((double)nTotalChildrenDataPoints);
		
		// Clustering this level nodes
		std::vector<CMLDataCluster> vClusters;
		CMLClustering_KMeans kMeans;
		kMeans.SetK(nK);
		nRet = kMeans.DoClustering(centerDataSet, centerWeights, vClusters);
		if (ML_FAILED(nRet))
			return nRet;
		
		// Pick up the clustering results
		for (i=0; i<nK; i++)
		{
			CMLDataCluster& cluster = vClusters[i];
			std::vector<CMLClustering_BIRCHCFTreeNode*> vpNodes;
			vpNodes.resize((size_t)cluster.dataset.Count());
			// Fill the nodes according to the center points
			int nCenterIndex;
			for (nCenterIndex=0; nCenterIndex<cluster.dataset.Count(); nCenterIndex++)
			{
				const CMLDataPoint& center = cluster.dataset.Get(nCenterIndex);
				vpNodes[nCenterIndex] = mapNodeCenters[center];
			}
			// Create the parent node
			vpParentNodes[i]->CreateFromChildNodes(vpNodes);
		}

		// Create the higher parent nodes
		nRet = ClusterParentNodes(vpParentNodes);
		if (ML_FAILED(nRet))
			return nRet;
	}
	return 0;
}

int CMLClustering_BIRCHCFTree::Release(void)
{
	return FreeNode(m_pRootNode);
}

int CMLClustering_BIRCHCFTree::FreeNode(CMLClustering_BIRCHCFTreeNode* pNode)
{
	if (pNode == NULL)
		return 0;
	int i;
	for (i=0; i<(int)pNode->GetNumChildNodes(); i++)
	{
		FreeNode(pNode->GetChildNode(i));
	}
	delete pNode;
	return 0;
}


///////////////////////////////////////////////////////////////////////////
// CMLClustering_BIRCH
CMLClustering_BIRCH::CMLClustering_BIRCH(void)
{
	m_nDataPointInitNumber = 1;
	m_nDataPointTotalNumber = 0;
	m_nLevelFactor = 2;
	m_dMaxMicroClusterRadius = 3.0;
}

CMLClustering_BIRCH::~CMLClustering_BIRCH(void)
{
}

int CMLClustering_BIRCH::SetParameters(const std::wstring& wstrParams)
{
	return 0;
}

int CMLClustering_BIRCH::Insert(const CMLDataPoint& dataPoint)
{
	int nRet;
	if (IsCFTreeCreated() == false)
	{
		m_DataSet.Insert(dataPoint);
		if (m_nDataPointTotalNumber >= m_nDataPointInitNumber -1)
		{
			// Do K-MEANS clustering to create micro-clusters
			nRet = InitMicroClusters();
			if (ML_FAILED(nRet))
				return nRet;
		}
		else
		{
			nRet = 0;
		}
	}
	else
	{
		// Insert to the MicroClusters
		nRet = InsertToMicroCluster(dataPoint);
		if (ML_FAILED(nRet))
			return nRet;
	}
	m_nDataPointTotalNumber++;
	return nRet;
}

int CMLClustering_BIRCH::GetClusters(const std::wstring& params, std::vector<CMLDataCluster>& vClusters)
{
	int nK = _wtoi(params.c_str());
	return CreateMacroClusters(nK, vClusters);
}

int CMLClustering_BIRCH::CreateCFTree(void)
{
	int nRet;
	m_CFTree.SetDistFunc(GetDistanceFunc());
	
	// Create CF-Tree from these micro-clusters
	nRet = m_CFTree.Create(m_vpMicroClusters, m_nLevelFactor);
	if (ML_FAILED(nRet))
		return nRet;

	return 0;
}

int CMLClustering_BIRCH::CreateMacroClusters(int nK, std::vector<CMLDataCluster>& vClusters)
{
	int i;
	// Create the dataset to prepare the clustering
	CMLDataSet centerDataSet;
	std::vector<double> centerWeights;
	int nTotalChildrenDataPoints = 0;

	centerDataSet.Resize((int)m_vpMicroClusters.size());
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		CMLDataPoint center = m_vpMicroClusters[i]->GetCenter();
		centerDataSet.Set(i, center);
		nTotalChildrenDataPoints += m_vpMicroClusters[i]->GetDataPointCount();
	}

	// Calculate the weights for the centers
	centerWeights.resize((int)m_vpMicroClusters.size());
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
		centerWeights[i] = ((double)(m_vpMicroClusters[i]->GetDataPointCount())) / ((double)nTotalChildrenDataPoints);

	// Clustering this level nodes
	CMLClustering_KMeans kMeans;
	kMeans.SetK(nK);
	return  kMeans.DoClustering(centerDataSet, centerWeights, vClusters);
}

int CMLClustering_BIRCH::InitMicroClusters()
{
	CMLClustering_KMeans kMeans;
	int nK = GetInitNumMicroClusters();

	// Initialize the k-means clustering method
	kMeans.SetDistanceFunc(GetDistanceFunc());
	kMeans.SetK(nK);

	// Use K-Means to create micro-clusters
	std::vector<CMLDataCluster> vClusters;
	int nRet = kMeans.DoClustering(m_DataSet, vClusters);
	if (ML_FAILED(nRet))
		return nRet;

	// Create the micro-clusters
	if (m_vpMicroClusters.empty() == false)
		ReleaseMicroClusters();
	m_vpMicroClusters.resize((size_t)nK);
	int i;
	for (i=0; i<nK; i++)
	{
		m_vpMicroClusters[i] = new CMLClustering_BIRCHMicroCluster();
		m_vpMicroClusters[i]->SetDistFunc(GetDistanceFunc());
		m_vpMicroClusters[i]->Create(vClusters[i].dataset);
	}

	return 0;
}

int CMLClustering_BIRCH::InsertToMicroCluster(const CMLDataPoint& dataPoint)
{
	int nRet;
	double dDist = 0;
	CMLClustering_BIRCHMicroCluster* pMicroCluster = FindNearestMicroCluster(dataPoint, dDist);
	ML_ASSERT(pMicroCluster != NULL);

	if (dDist > m_dMaxMicroClusterRadius)
	{
		if (GetNumMicroClusters() >= m_nMaxNumMicroClusters)
		{
			// Merger two closest micro-cluster
			nRet = MergeClosestTwoMicroClusters();
			ML_ON_FAILED_RETURN(nRet);
		}

		// Create a new micro-cluster
		CMLDataSet dataSet;
		dataSet.Insert(dataPoint);
		CMLClustering_BIRCHMicroCluster* pNewMicroCluster = new CMLClustering_BIRCHMicroCluster();
		pNewMicroCluster->SetDistFunc(GetDistanceFunc());
		pNewMicroCluster->Create(dataSet);
		m_vpMicroClusters.push_back(pNewMicroCluster);
	}
	else
	{
		// Insert into the micro-cluster
		nRet = pMicroCluster->Insert(dataPoint);
		if (ML_FAILED(nRet))
			return nRet;
	}
	return 0;
}


CMLClustering_BIRCHMicroCluster* CMLClustering_BIRCH::FindNearestMicroCluster(const CMLDataPoint& point, double& dDist)
{
	int i;
	double dMinDist = DBL_MAX;
	CMLClustering_BIRCHMicroCluster* pNearestMicroCluster = NULL;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		double dDist = m_pDistFunc->Distance(point, m_vpMicroClusters[i]->GetCenter());
		if (dDist < dMinDist)
		{
			pNearestMicroCluster = m_vpMicroClusters[i];
			dMinDist = dDist;
		}
	}
	dDist = dMinDist;
	return pNearestMicroCluster;
}

int CMLClustering_BIRCH::MergeClosestTwoMicroClusters(void)
{
	// Find two closest clusters
	double dMinDist = DBL_MAX;
	CMLClustering_BIRCHMicroCluster* pCluster1 = NULL;
	CMLClustering_BIRCHMicroCluster* pCluster2 = NULL;
	int nIndex1, nIndex2;
	int nNumCluster = (int)m_vpMicroClusters.size();
	if (nNumCluster < 2)
		return -1;
	int i,j;
	for (i=0; i<nNumCluster-1; i++)
	{
		for (j=i+1; j<nNumCluster; j++)
		{
			double dDist = m_pDistFunc->Distance(m_vpMicroClusters[i]->GetCenter(), m_vpMicroClusters[j]->GetCenter());
			if (dDist < dMinDist)
			{
				nIndex1 = i;
				nIndex2 = j;
				dMinDist = dDist;
			}
		}
	}
	// Merge two micro-clusters
	pCluster1 = m_vpMicroClusters[nIndex1];
	pCluster2 = m_vpMicroClusters[nIndex2];
	for (i=0; i<pCluster2->GetDataPointCount(); i++)
	{
		pCluster1->Insert(pCluster2->GetDataPoint(i));
	}
	delete pCluster2;
	m_vpMicroClusters.erase(m_vpMicroClusters.begin() + nIndex2);
	return 0;
}


int CMLClustering_BIRCH::ReleaseMicroClusters()
{
	int i;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		if (m_vpMicroClusters[i] != NULL)
		{
			delete m_vpMicroClusters[i];
			m_vpMicroClusters[i] = NULL;
		}
	}
	m_vpMicroClusters.clear();
	return 0;
}

_MYLABLIB_END